package com.base.graph;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 630. 课程表 III (困难)
 * 带反悔的贪心：
 * 贪心策略为，优先选择结束时间早的课程
 * 这里有 n 门不同的在线课程，按从 1 到 n编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
 * <p>
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 * <p>
 * 返回你最多可以修读的课程数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月14日 18:52
 */
public class ScheduleCourse {

    public int scheduleCourse(int[][] courses) {
        // 当前已经过去天数,初始值为第0
        int day = 0;
        // 以 a[1] 从小到大排序
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);

        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 0; i < courses.length; i++) {
            int duration = courses[i][0];
            int end = courses[i][1];

            if (day + duration <= end) {
                day += duration;
                heap.add(duration);
            } else if (!heap.isEmpty() && heap.peek() > duration) {
                day -= heap.poll();
                day += duration;
                heap.add(duration);
            }

        }
        return heap.size();

    }
}